package sort;

import java.util.Arrays;

public class Sorting {
    public static void main(String[] args) {
        int[] a = new int[]{9, 0, 4, 5, 90, 10, 99, 12, 15, 91};
        /*
        System.out.println("Bubble sort:");
        bubbleSort(a);
        */

        /*
        System.out.println("Straight selection sort:");
        straightSelectionSort(a);
        */

        /*
        System.out.println("Insertion sort");
        insertionSort(a);
        */

        int n =239;
        int numberOfDigits = (int)Math.log10(n)+1;
        System.out.println("The heapsort:");
        heapsort(a);
        System.out.println(Arrays.toString(a));
    }

    public static void insertionSort(int[] a, int left, int right){
        for (int i = left+1; i <= right; i++) {
            int temp = a[i];
            int j = i - 1;
            while (j >= left && a[j] > temp) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = temp;
        }
    }
    public static void insertionSort(int[] a) {
       insertionSort(a,0, a.length-1);
    }

    private static void bubbleSort(int[] a) {
        int n = a.length;
        while (n > 0) {
            int newn = 0;
            for (int i = 1; i < n; i++) {
                if (a[i - 1] > a[i]) {
                    swap(a, i - 1, i);
                    newn = i;
                }
            }
            n = newn;
        }
    }

    private static void straightSelectionSort(int[] a) {
        for (int i = 0; i < a.length - 1; i++)
            for (int j = i + 1; j < a.length; j++)
                if (a[i] > a[j]) swap(a, i, j);
    }

    private static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    private static void mergeSort(int[] a, int left, int right) {
        if (a == null) return;
        if (left == right) return;
        if (left + 1 == right) {
            if (a[left] > a[right]) swap(a, left, right);
        }

        int middle = left + (right - left) / 2;
        mergeSort(a, left, middle);
        mergeSort(a, middle + 1, right);

        int[] buff = new int[right - left + 1];
        for (int i = 0, p = left, q = middle + 1; i < (right - left + 1); i++) {
            if (q > right || p <= middle && a[p] < a[q]) {
                buff[i] = a[p++];
            } else
                buff[i] = a[q++];
        }
        System.arraycopy(buff, 0, a, left, (right - left + 1));
    }

    private static void heapsort(int[] a) {
        for (int i = a.length / 2; i >= 0; i--) siftDown(a, i, a.length - 1);
        for (int i = a.length - 1; i > 0; i--) {
            swap(a, 0, i);
            siftDown(a, 0, i - 1);
        }
    }

    /**
     * |
     * Searches the next position for a given element in a heap
     *
     * @param a the array to store the binary heap
     * @param i the index of the element to sift down
     * @param n the size of a heap at the moment
     */
    private static void siftDown(int[] a, int i, int n) {
        int value = a[i];
        for (int j = 2 * i + 1; j <= n; i = j, j = 2 * i + 1) {
            if (j < n && a[j] < a[j + 1]) j++;
            if (a[j] <= value) break;
            a[i] = a[j];
        }
        a[i] = value;
    }

}
